package 链表.链表基础;

import 链表.ListNode;

/**
 * @Project: Data Structure and Algorithms
 * @Package: 链表.链表基础
 * @ClassName: t206
 * @Author: zhouyihe
 * @Date: 2025/11/28 21:19
 * @Description: 反转链表
 */
public class t206 {
    // 递归实现
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newListNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newListNode;
    }

    public static ListNode reverseList1(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // for test
    // 打印链表的方法
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建一个测试链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        // 打印原始链表
        System.out.println("原始链表：");
        printList(head);

        // 执行算法
        ListNode reversedHead = reverseList1(head);

        // 结果链表
        System.out.println("结果链表：");
        printList(reversedHead);
    }
}

